#pragma once

#include "algorithm"
#include "math.h"
#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 *
 *给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

 * */
/**
 *  暴力string 反而超时
 *  1位 9-1+1 )*1 =9
 *  2位 99-10+1)*2 =2*90    10 - 99
 *
 *  3位 999-100+1)*3=3*900  100 999
 *
 *
 *
 *
 * */
int findNthDigit(int n) {
    //获取n跑在哪个区间
// 1位 - 9个  = 共9位
    // 2位- 90个 = 共180位
    // 3位- 900个 = 共2700位
    // 4 位- 9000个 = 共36000位
    int i;
    for (i = 1; i < 11; ++i) {
        if (n - i * 9 * pow(10, i - 1) <= 0)
            break;
        n -= i * 9 * pow(10, i - 1);
    }

    // 0-indexed program method
    --n;
    int x = n % i;
    int y = pow(10, i - 1) + n / i;
    string s = to_string(y);
    return s[x] - '0';

}